/*
 * expression.c
 *
 *  Created on: Jan 9, 2012
 *      Author: liuhaifeng
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <dataset.h>
#include <expression.h>

#define EXP_QUOTE             ('"')
#define EXP_IDENT_LEAD        ('%')
#define EXP_SYMBOL_NOT        ('!')
#define EXP_SYMBOL_AND        ('&')
#define EXP_SYMBOL_OR         ('|')
#define EXP_SYMBOL_EQUAL      ('=')
#define EXP_SYMBOL_START_WITH ('[')
#define EXP_SYMBOL_CONTAINS   ('*')
#define EXP_SYMBOL_END_WITH   (']')

#define EXP_TO_OPR(c) \
	((c) == '(' ? EXP_OPR_PARENTHESIS_OPEN : \
	(c) == '=' ? EXP_OPR_EQUALS : \
	(c) == '[' ? EXP_OPR_START_WITH : \
	(c) == '*' ? EXP_OPR_CONTAINS : \
	(c) == ']' ? EXP_OPR_END_WITH : \
	(c) == '&' ? EXP_OPR_AND : \
	(c) == '|' ? EXP_OPR_OR : \
	(c) == '!' ? EXP_OPR_NOT : \
	(c) == ')' ? EXP_OPR_PARENTHESIS_CLOSE : \
	(c) == '#' ? EXP_OPR_TERM : \
	EXP_OPR_UNKNOWN)

#define EXP_TO_OPR_CHAR(o) \
	((o) == EXP_OPR_PARENTHESIS_OPEN ? '('  : \
	(o) == EXP_OPR_EQUALS ? '=' : \
	(o) == EXP_OPR_START_WITH ? '[' : \
	(o) == EXP_OPR_CONTAINS ? '*' : \
	(o) == EXP_OPR_END_WITH ? ']' : \
	(o) == EXP_OPR_AND ? '&' : \
	(o) == EXP_OPR_OR ? '|' : \
	(o) == EXP_OPR_NOT ? '!' : \
	(o) == EXP_OPR_PARENTHESIS_CLOSE ? ')' : \
	(o) == EXP_OPR_TERM ? '#' : \
	'?')

/**
 * The priority of operators:
 * 6: FUNCTIONs
 * 5: )
 * 4: !
 * 3: & |
 * 2: = [ * ]
 * 1: (
 * 0: #
 */
#define EXP_OPR_PRIORITY(o) \
	((o) == EXP_OPR_PARENTHESIS_CLOSE ? 0 : \
	((o) == EXP_OPR_AND || (o) == EXP_OPR_OR) ? 1 : \
	((o) == EXP_OPR_EQUALS \
		|| (o) == EXP_OPR_START_WITH \
		|| (o) == EXP_OPR_CONTAINS \
		|| (o) == EXP_OPR_END_WITH) ? 2 : \
	(o) == EXP_OPR_NOT ? 3 : \
	(o) == EXP_OPR_PARENTHESIS_OPEN ? 4 : \
	EXP_OPR_UNKNOWN)

static inline Expression * _exp_new(int type) {
	Expression *exp = (Expression *) awl_alloc(sizeof(Expression));
	memset(exp, 0, sizeof(Expression));
	exp->type = type;
	return exp;
}

static inline Expression * _exp_new_constant(const char *constant) {
	Expression *exp = _exp_new(EXP_CONSTANT);
	strncpy(exp->exp.constant, constant, EXP_MAX_CONSTANT);
	return exp;
}

static inline Expression * _exp_new_ident(const char *ident) {
	Expression *exp = _exp_new(EXP_IDENTITY);
	strncpy(exp->exp.ident, ident, EXP_MAX_IDENTITY);
	return exp;
}

static inline Expression * _exp_new_unary(int opr, Expression *a) {
	Expression *exp = _exp_new(EXP_UNARY);
	exp->exp.unary.opr = opr;
	exp->exp.unary.a = a;
	return exp;
}

static inline Expression * _exp_new_bigram(int opr, Expression *a,
		Expression *b) {
	Expression *exp = _exp_new(EXP_BIGRAM);
	exp->exp.bigram.opr = opr;
	exp->exp.bigram.a = a;
	exp->exp.bigram.b = b;
	return exp;
}

static const char * _exp_string_until(char *buf, const char *src,
		const char stop, unsigned int buf_len) {
	int i = 0;
	while (src != NULL && *src != stop && *src != 0 && i < buf_len - 1) {
		switch (*src) {
		case '\\':
			src++;
			switch (*src) {
			case 0:
				return NULL;
				break;
			case 't':
				buf[i] = '\t';
				break;
			case 'n':
				buf[i] = '\n';
				break;
			case 'r':
				buf[i] = '\r';
				break;
			default:
				if (*src == stop)
					return NULL;
				buf[i] = *src;
				break;
			}
			break;
		default:
			buf[i] = *src;
			break;
		}
		src++;
		i++;
	}
	buf[i] = 0;
	return src;
}

static const char * _exp_parse_ident(char *buf, const char *src,
		const unsigned int buf_len) {
	int i = 0;

	while (*src != 0
			&& (*src == '_' || (*src >= 'a' && *src <= 'z') || (*src >= 'A' && *src <= 'Z')
					|| (*src >= '0' && *src <= '9')) && i < buf_len - 1) {
		buf[i++] = *src++;
	}

	buf[i] = 0;
	return src;
}

static const char * _exp_parse_number(char *buf, const char *src,
		const unsigned int buf_len) {
	int i = 0;
	int state = 0; /* 0 start or before dot, 1 dot, 2 after dot */

	while (*src != 0 && ((*src >= '0' && *src <= '9') || *src == '.')
			&& i < buf_len - 1) {
		if (*src == '.') {
			if (state == 0)
				state = 1;
			else
				return NULL;
		}
		buf[i++] = *src++;
	}

	if (state != 0 && state != 2)
		return NULL;

	buf[i] = 0;
	return src;
}

static ExpToken * _exp_new_token(int type, const char *content) {
	ExpToken *token = (ExpToken *) awl_alloc(sizeof(ExpToken));
	token->type = type;
	strncpy(token->content, content, EXP_MAX_TOKEN);
	return token;
}

static void _exp_destroy_tokens(list *tokens) {
	ExpToken *token;

	move_head(tokens);
	while ((token = next(tokens)) != NULL) {
		awl_free(token);
	}
	destroy_list(tokens);
}

static const char * _exp_parse_token(list *tokens, const char *str,
		const char stop) {
	char buf[EXP_MAX_TOKEN];
	ExpToken *token;

	while (str != NULL && *str != 0 && *str != stop) {
		switch (*str) {
		case '(':
		case ')':
		case '!':
		case '&':
		case '|':
		case '=':
		case '[':
		case '*':
		case ']':
			buf[0] = *str;
			buf[1] = 0;
			token = _exp_new_token(EXP_TOKEN_OPR, buf);
			push(tokens, token);
			str++;
			break;
		case '"':
			str = _exp_string_until(buf, ++str, '"', EXP_MAX_TOKEN);
			if (str == NULL || *str != '"') {
				fputs("Invalid constant string.\n", stderr);
				return NULL;
			}
			token = _exp_new_token(EXP_TOKEN_CONST, buf);
			push(tokens, token);
			str++;
			break;
		case ' ':
			str++;
			break;
		case ',':
			token = _exp_new_token(EXP_TOKEN_COMMA, ",");
			push(tokens, token);
			str++;
			break;
		default:
			if (*str == '_' || (*str >= 'a' && *str <= 'z') || (*str >= 'A' && *str <= 'Z')) {
				str = _exp_parse_ident(buf, str, EXP_MAX_TOKEN);
				if (str == NULL) {
					fputs("Invalid identity string.\n", stderr);
					return NULL;
				}
				token = _exp_new_token(EXP_TOKEN_IDENT, buf);
				push(tokens, token);
			} else if (*str >= '0' && *str <= '9') {
				str = _exp_parse_number(buf, str, EXP_MAX_TOKEN);
				if (str == NULL) {
					fputs("Invalid number string.\n", stderr);
					return NULL;
				}
				token = _exp_new_token(EXP_TOKEN_CONST, buf);
				push(tokens, token);
			} else {
				fputs("Failed to parse expression.\n", stderr);
				return NULL;
			}
			break;
		}
	}
	return str;
}

static inline void _exp_destroy_exp_stack(list *stack) {
	Expression *exp;

	move_head(stack);
	while ((exp = next(stack)) != NULL) {
		exp_destroy(exp);
	}
	destroy_list(stack);
}

static inline int _exp_check_opr(ExpOperator opr, list *opr_stack,
		list *exp_stack) {
	ExpOperator *tmp_opr, last_opr = EXP_OPR_UNKNOWN;
	Expression *tmp_exp;

	while ((tmp_opr = (ExpOperator *) tail(opr_stack)) != NULL
			&& *tmp_opr != EXP_OPR_UNKNOWN
			&& *tmp_opr != EXP_OPR_PARENTHESIS_OPEN
			&& EXP_OPR_PRIORITY(opr) <= EXP_OPR_PRIORITY(*tmp_opr)) {
		last_opr = *tmp_opr;
		pop(opr_stack);
		switch (last_opr) {
		case EXP_OPR_NOT:
			if (count_list(exp_stack) < 1)
				return -1;
			tmp_exp = _exp_new_unary(EXP_OPR_NOT, (Expression *) pop(exp_stack));
			push(exp_stack, tmp_exp);
			break;
		case EXP_OPR_EQUALS:
		case EXP_OPR_START_WITH:
		case EXP_OPR_CONTAINS:
		case EXP_OPR_END_WITH:
		case EXP_OPR_AND:
		case EXP_OPR_OR:
			if (count_list(exp_stack) < 2)
				return -2;
			tmp_exp = (Expression *) pop(exp_stack);
			tmp_exp = _exp_new_bigram(last_opr, (Expression *) pop(exp_stack),
					tmp_exp);
			push(exp_stack, tmp_exp);
			break;
		case EXP_OPR_PARENTHESIS_CLOSE:
		default:
			return -3;
			break;
		}
	}
	if (opr == EXP_OPR_PARENTHESIS_CLOSE) {
		if (last_opr == EXP_OPR_PARENTHESIS_OPEN)
			pop(opr_stack);
		else
			return -4;
	} else if (opr != EXP_OPR_TERM) {
		ExpOperator *o = (ExpOperator *) awl_alloc(sizeof(ExpOperator));
		*o = opr;
		push(opr_stack, o);
	}
	return 0;
}

static inline void _exp_destroy_opr_stack(list *stack) {
	ExpOperator *opr;

	move_head(stack);
	while ((opr = next(stack)) != NULL) {
		awl_free(opr);
	}
	destroy_list(stack);
}

static inline void _exp_destroy_stack(list *opr_stack, list *exp_stack) {
	_exp_destroy_opr_stack(opr_stack);
	_exp_destroy_exp_stack(exp_stack);
}

/**
 * Parse source to expression, functions are not support.
 */
static int _exp_parse_exp(Expression **exp, list *tokens) {
	list *opr_stack, *exp_stack;
	ExpToken *token;
	int state = 0; /* 0: wait for exp, 1 wait for bigram operator */
	ExpOperator opr, last_opr, *tmp_o;
	Expression *tmp_exp, *tmp_exp2;
	int ret;

	opr_stack = create_list();
	exp_stack = create_list();

	token = (ExpToken *) current(tokens);
	while (token != NULL) {
		switch (token->type) {
		case EXP_TOKEN_CONST:
			if (state != 0) {
				fprintf(stderr, "Invalid expression, unexpected constant.\n");
				_exp_destroy_stack(opr_stack, exp_stack);
				return -1;
			}
			push(exp_stack, _exp_new_constant(token->content));
			state = 1;
			break;
		case EXP_TOKEN_IDENT:
			if (state != 0) {
				fprintf(stderr, "Invalid expression, unexpected identity.\n");
				_exp_destroy_stack(opr_stack, exp_stack);
				return -1;
			}
			push(exp_stack, _exp_new_ident(token->content));
			state = 1;
			break;
		case EXP_TOKEN_OPR:
			opr = EXP_TO_OPR(token->content[0]);
			if (opr == EXP_OPR_UNKNOWN) {
				fprintf(stderr, "Invalid expression, unknown operator.\n");
				_exp_destroy_stack(opr_stack, exp_stack);
				return -1;
			}
			switch (opr) {
			case EXP_OPR_NOT:
				if (state != 0) {
					fprintf(stderr, "Invalid expression, unexpected unary operator.\n");
					_exp_destroy_stack(opr_stack, exp_stack);
					return -1;
				}
				tmp_o = (ExpOperator *) awl_alloc(sizeof(ExpOperator));
				*tmp_o = opr;
				push(opr_stack, tmp_o);
				break;
			case EXP_OPR_EQUALS:
			case EXP_OPR_START_WITH:
			case EXP_OPR_CONTAINS:
			case EXP_OPR_END_WITH:
			case EXP_OPR_AND:
			case EXP_OPR_OR:
				if (state != 1
						|| _exp_check_opr(opr, opr_stack, exp_stack) != 0) {
					fprintf(stderr, "Invalid expression, unexpected operator.\n");
					_exp_destroy_stack(opr_stack, exp_stack);
					return -1;
				}
				state = 0;
				break;
			case EXP_OPR_PARENTHESIS_OPEN:
				if (state == 0) {
					tmp_o = (ExpOperator *) awl_alloc(sizeof(ExpOperator));
					*tmp_o = opr;
					push(opr_stack, tmp_o);
				} else if (count_list(exp_stack) > 0
						&& ((Expression *) tail(exp_stack))->type == EXP_IDENTITY) {
					// parse function
					tmp_exp = (Expression *) pop(exp_stack);
					strncpy(tmp_exp->exp.func.name, tmp_exp->exp.ident, EXP_MAX_IDENTITY);
					tmp_exp->type = EXP_FUNCTION;
					tmp_exp->exp.func.parameters = create_list();
					push(exp_stack, tmp_exp);

					token = next(tokens);
					while (token != NULL) {
						if (token->type == EXP_TOKEN_OPR
								&& token->content[0] == EXP_TO_OPR_CHAR(EXP_OPR_PARENTHESIS_CLOSE)) {
							break;
						} else if (token->type == EXP_TOKEN_COMMA) {
							if (count_list(tmp_exp2->exp.func.parameters) < 1) {
								_exp_destroy_stack(opr_stack, exp_stack);
								return -1;
							}
							token = (ExpToken *) next(tokens);
							continue;
						}
						ret = _exp_parse_exp(&tmp_exp2, tokens);
						token = (ExpToken *) current(tokens);
						if (ret == -1) {
							_exp_destroy_stack(opr_stack, exp_stack);
							return -1;
						}
						push(tmp_exp->exp.func.parameters, tmp_exp2);
					}
					if (ret != 0
							|| token->type != EXP_TOKEN_OPR
							|| token->content[0] != EXP_TO_OPR_CHAR(EXP_OPR_PARENTHESIS_CLOSE)) {
						_exp_destroy_stack(opr_stack, exp_stack);
						return -1;
					}
				} else {
					fprintf(stderr, "Invalid expression, unexpected \"(\"\n");
					_exp_destroy_stack(opr_stack, exp_stack);
					return -1;
				}
				break;
			case EXP_OPR_PARENTHESIS_CLOSE:
				if (state != 1 || _exp_check_opr(opr, opr_stack, exp_stack) != 0) {
					goto END;
				}
				break;
			default:
				break;
			}
			break;
		case EXP_TOKEN_COMMA:
		default:
			goto END;
			break;
		}

		token = next(tokens);
	}

END:
	if (state != 1) {
		fprintf(stderr, "Invalid expression, unexpected end.\n");
		_exp_destroy_stack(opr_stack, exp_stack);
		return -1;
	} else if (_exp_check_opr(EXP_OPR_TERM, opr_stack, exp_stack) != 0) {
		fprintf(stderr, "Invalid expression, failed to parse.\n");
		_exp_destroy_stack(opr_stack, exp_stack);
		return -1;
	} else if (count_list(opr_stack) < 1 && count_list(exp_stack) == 1) {
		*exp = (Expression *) pop(exp_stack);
		_exp_destroy_stack(opr_stack, exp_stack);
		return 0;
	} else {
		//fprintf(stderr, "Invalid expression, unexpected token. state = %d\n", state);
		*exp = (Expression *) pop(exp_stack);
		_exp_destroy_stack(opr_stack, exp_stack);
		return 1;
	}
}

const char * exp_parse(Expression **exp, const char *src, const char stop) {
	list *tokens = create_list();
	ExpToken *token;
	int ret;

	if ((src = _exp_parse_token(tokens, src, stop)) == NULL) {
		_exp_destroy_tokens(tokens);
		return NULL;
	}

	move_head(tokens);
	next(tokens);
	ret = _exp_parse_exp(exp, tokens);
	_exp_destroy_tokens(tokens);

	if (ret == -1)
		return NULL;

	return src;
}

static int _exp_eval(char *ret, Expression *exp, IdentEval ident_eval,
		FuncEval func_eval, void *env);

static int _exp_eval_const(BOOL *ret, const char *constant) {
	if (constant == NULL)
		return -1;

	if (strcmp(constant, "") == 0 || strcmp(constant, "NULL") == 0
			|| strcmp(constant, "FALSE") == 0 || strcmp(constant, "null") == 0
			|| strcmp(constant, "False") == 0 || strcmp(constant, "false") == 0
			|| strcmp(constant, "No") == 0 || strcmp(constant, "no") == 0
			|| strcmp(constant, "0") == 0)
		*ret = FALSE;
	else
		*ret = TRUE;

	return 0;
}

static int _exp_eval_unary(BOOL *ret, ExpUnary *unary, IdentEval ident_eval,
		FuncEval func_eval, void *env) {
	char tmp[EXP_MAX_STRING];

	if (unary == NULL || unary->a == NULL)
		return -1;

	switch (unary->opr) {
	case EXP_OPR_YES:
		if (_exp_eval(tmp, unary->a, ident_eval, func_eval, env) != 0)
			return -2;
		if (_exp_eval_const(ret, tmp) != 0)
			return -2;
		break;
	case EXP_OPR_NOT:
		if (_exp_eval(tmp, unary->a, ident_eval, func_eval, env) != 0)
			return -3;
		if (_exp_eval_const(ret, tmp) != 0)
			return -3;
		*ret = !*ret;
		break;
	default:
		return -4;
		break;
	}
	return 0;
}

static int _exp_eval_bigram(BOOL *ret, ExpBigram *bigram, IdentEval ident_eval,
		FuncEval func_eval, void *env) {
	char a[EXP_MAX_STRING], b[EXP_MAX_STRING], *p;
	BOOL ba, bb;
	int i;

	if (bigram == NULL || bigram->a == NULL || bigram->b == NULL)
		return -1;
	if (_exp_eval(a, bigram->a, ident_eval, func_eval, env) != 0)
		return -2;
	if (_exp_eval(b, bigram->b, ident_eval, func_eval, env) != 0)
		return -3;

	switch (bigram->opr) {
	case EXP_OPR_AND:
	case EXP_OPR_OR:
		if (_exp_eval_const(&ba, a) != 0)
			return -4;
		if (_exp_eval_const(&bb, b) != 0)
			return -5;
		*ret = (bigram->opr == EXP_OPR_AND) ? (ba && bb) : (ba || bb);
		break;
	case EXP_OPR_EQUALS:
		*ret = (strcmp(a, b) == 0);
		break;
	case EXP_OPR_START_WITH:
		i = 0;
		while (a[i] == b[i] && b[i] != 0)
			i++;
		*ret = (b[i] == 0);
		break;
	case EXP_OPR_CONTAINS:
		*ret = (strstr(a, b) != NULL);
		break;
	case EXP_OPR_END_WITH:
		i = strlen(a) - strlen(b);
		if (i < 0) {
			*ret = FALSE;
		} else {
			p = a + i;
			*ret = (strcmp(p, b) == 0);
		}
		break;
	default:
		return -4;
		break;
	}
	return 0;
}

static int _exp_eval(char *ret, Expression *exp, IdentEval ident_eval,
		FuncEval func_eval, void *env) {
	BOOL tmp;

	if (exp == NULL)
		return -1;

	switch (exp->type) {
	case EXP_CONSTANT:
		strncpy(ret, exp->exp.constant, EXP_MAX_STRING);
		break;
	case EXP_IDENTITY:
		if (ident_eval(ret, exp->exp.ident, env) != 0)
			return -3;
		break;
	case EXP_FUNCTION:
		if (func_eval(ret, &exp->exp.func, ident_eval, env) != 0)
			return -4;
		break;
	case EXP_UNARY:
		if (_exp_eval_unary(&tmp, &exp->exp.unary, ident_eval, func_eval, env)
				!= 0)
			return -5;
		sprintf(ret, "%d", tmp);
		break;
	case EXP_BIGRAM:
		if (_exp_eval_bigram(&tmp, &exp->exp.bigram, ident_eval, func_eval, env)
				!= 0)
			return -6;
		sprintf(ret, "%d", tmp);
		break;
	default:
		return -7;
		break;
	}

	return 0;
}

int exp_eval(BOOL *ret, Expression *exp, IdentEval ident_eval,
		FuncEval func_eval, void *env) {
	char buf[EXP_MAX_STRING];

	if (_exp_eval(buf, exp, ident_eval, func_eval, env) != 0)
		return -1;

	if (_exp_eval_const(ret, buf) != 0)
		return -1;

	return 0;
}

void exp_destroy(Expression *exp) {
	Expression *e;

	if (exp != NULL) {
		switch (exp->type) {
		case EXP_FUNCTION:
			move_head(exp->exp.func.parameters);
			while ((e = (Expression *) next(exp->exp.func.parameters)) != NULL) {
				exp_destroy(e);
			}
			destroy_list(exp->exp.func.parameters);
			break;
		case EXP_UNARY:
			exp_destroy(exp->exp.unary.a);
			break;
		case EXP_BIGRAM:
			exp_destroy(exp->exp.bigram.a);
			exp_destroy(exp->exp.bigram.b);
			break;
		case EXP_CONSTANT:
		case EXP_IDENTITY:
		default:
			break;
		}
		awl_free(exp);
	}
}

